package ch5.part9;

/**
 * 字符串删除k个数字之后，值最小
 * 时间复杂度：O(n) = n
 * 空间复杂度：O(n) = n
 *
 * @author liuwanxiang
 * @version 2019/06/17
 */
public class RemoveDigits {

    private static String removeDigitV1(String num, int k) {
        int newLength = num.length() - k;
        if (newLength <= 0) {
            return "0";
        }
        // 构建char栈
        char[] stack = new char[newLength];
        // 记录栈顶Index位置
        int top = 0;
        for (int i = 0; i < num.length(); i++) {
            // 取得该位置char值
            char c = num.charAt(i);
            // 栈顶元素大于char值，且此时的k值还未减够
            // 删除栈顶元素，待减数字个数k-1
            // 循环删除，直到不满足条件
            while (top > 0 && stack[top - 1] > c && k > 0) {
                top--;
                k--;
            }
            // 空栈时，0不入栈
            if ('0' == c && top == 0) {
                newLength--;
                if (newLength < 0) {
                    return "0";
                }
                continue;
            }
            // char值入栈
            stack[top++] = c;
        }
        return new String(stack, 0, newLength);
    }

    public static void main(String[] args) {

        System.out.println(removeDigitV1("1593212", 3));
        System.out.println(removeDigitV1("30200", 1));
        System.out.println(removeDigitV1("10", 2));
        System.out.println(removeDigitV1("541270936", 3));
        System.out.println(removeDigitV1("1593212", 4));

    }

}
